1. Field of the Invention
The present invention relates generally to coordination amongst execution sequences in a multiprocessor computer, and more particularly, to structures and techniques for facilitating nonblocking implementations of shared data structures.
2. Description of the Related Art
A traditional way to implement shared data structures is to use mutual exclusion (locks) to ensure that concurrent operations do not interfere with one another. However, locking has a number of disadvantages with respect to software engineering, fault-tolerance, and scalability. As a result, researchers have investigated a variety of alternative nonblocking synchronization techniques that do not employ mutual exclusion. A synchronization technique is said to be wait-free if it ensures that every thread will continue to make progress in the face of arbitrary delay (or even failure) of other threads. It is said to be lock-free if it ensures only that some thread always makes progress. While wait-free synchronization is the ideal behavior (thread starvation is unacceptable), lock-free synchronization is often good enough for practical purposes (as long as starvation, while possible in principle, never happens in practice).
In the hands of a highly skilled programmer, the synchronization primitives provided by many modern processor architectures, such as compare-and-swap (CAS) operations or load-locked/store-conditional (LL/SC) operation pairs, are typically powerful enough to achieve wait-free (or lock-free) implementations of a linearizable data object. Nevertheless, with a few exceptions, wait-free and lock-free data structures are rarely used in practice. The underlying problem is that conventional synchronization primitives such as CAS and LL/SC are an awkward match for lock-free synchronization. These primitives lend themselves most naturally to optimistic synchronization, which guarantees progress only in the absence of synchronization conflicts. For example, the natural way to use CAS for synchronization is to read a value v from an address a, perform a multistep computation to derive a new value w, and then to call CAS to reset the value of a from v to w. The CAS is successful if the value at a has not been changed in the meantime. Progress guarantees typically rely on complex and computationally expensive “helping” mechanisms that pose a substantial barrier to the wider use of lock-free synchronization.
Accordingly, alternative techniques are desired whereby these complexities and related computational expense may be avoided or reduced. In this way, nonblocking shared data objects may achieve wider adoption and use.